/**
 * 选/不选 每个物品可以选多个
 * 区别： 遍历顺序上 
 * 01:遍历容量是倒序-保证每个物品只拿一个，
 * 完全:遍历是正序-物品可以拿很多个
 * 
 * 思考遍历层级，可以先物品，后容量；也可以先容量，后物品
 */
/**
 * 相关题目
 * 单词拆分
 * 零钱兑换1,2
 * 完全平方数
 * 组合总和
 */
/**
 * 二维数组实现
 */
const CompletePack02 = (values, weights, w) => {
  const m = values.length;

  //（1）额外的一行i=0表示没有物品可选
  //（2）额外的一列来j=0 表示背包没有容量
  const dp = Array(m+1).fill().map(()=> Array(w+1).fill(0))

  //遍历物品 1～m件
  for (let i = 1; i <= m; i++) {
    //已经初始化过j=0;所以从1～w容量开始记录
    for (let j = 1; j <= w; j++) {
      if (j < weights[i - 1]) {
        //!一件也装不下
        dp[i][j] = dp[i - 1][j]; 
      } else {
        /**
         * 物品i可以放入无限k次，dp[i-1][j-k*weights[i]]+k*values[i]
         *! 第k次可以用k-1次表示：dp[i][j]=dp[i][j - weights[i - 1]]+values[i] 这样可以代表i取了多次
         */
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weights[i - 1]] + values[i - 1]);
      }
    }
  }

  return dp[m][w];
};

/**
 * 一维数组实现 
 */
const CompletePack= (values, weights, w) =>  {
  const dp = Array(w+1).fill(0);

  for(let i=0;i<values.length;i++){
    //!容量正序可以表示放入多次
    for(let j=weights[i]; j<=w;j++){
      dp[j] = Math.max(dp[j], dp[j-weights[i]]+values[i]);
    }
  }
  return dp[w];
}
const values = [15, 20, 30];
const weights = [1, 3, 4];
const w = 4;
console.log('完全背包', CompletePack(values, weights, w)); //60

/**
 * review 1211✅
 */


console.log('完全背包', CompletePack02(values, weights, w)); //60


